package com.jhy.review.day08;

/**
 * 2022年9月1日10:15:53
 * 归并排序、
 *
 *归并排序的主要思想是递归的思想
 * 先从找到中点
 * 然后
 * 左边的排好序
 * 右边的排好序
 * 最后merge
 * 时间复杂度O(N*logN)，额外空间复杂度O(N）
 */
public class Code01_MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
//        先左边有序
        mergeSort(arr, l, mid);
//        在右边有序
        mergeSort(arr, mid + 1, r);
//        合并
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int i = 0;
//        左边的指针
        int p1 = l;
//        右边的指针
        int p2 = m + 1;
//        当左边的指针和右边的指针都没有越界的情况下
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
//        p2不满足条件了 p1直接赋值了
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
//        同理
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
//        然后在给arr赋值
        for (i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,2,1,2,8,2,1};
       mergeSort(arr);
       printArray(arr);

    }
    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}
